Evolvable Hardware or EHW is reconfigurable hardware that self-configures under the control of an evolutionary algorithm. In evolutionary electronics, the search for an electronic circuit reconfiguration can be made in software and the final solution downloaded or become a blueprint for hardware, which is referred to as extrinsic evolution. Alternatively, evolution can be performed directly in hardware, referred to as intrinsic evolution. With intrinsic evolution, solutions may be evolved directly on a chip.
The main steps of evolutionary synthesis are illustrated in FIG. 1. First, a population of chromosomes is randomly generated. The chromosomes are converted into circuit models for extrinsic EHW, or control bit strings downloaded to programmable hardware for intrinsic EHW. Circuit responses are compared against specifications of a target response, and individuals are ranked based on how close they come to satisfying it. In preparation for a new iteration loop, a new population of individuals is generated from the pool of best individuals in the previous generation, some of these individuals are taken as they were and some are modified by genetic operators such as chromosome crossover and mutation. This process is repeated for many generations, and results in increasingly better individuals. Such a process is usually stopped after a number of generations, or when the closeness to the target response has reached a sufficient degree. One of several solutions may be found among the individuals of the last generation.
A variety of circuits have been synthesized through extrinsic evolutionary means. For example, Koza et al., in U.S. Pat. No. 5,867,397, issued on Feb. 2, 1999, entitled METHOD AND APPARATUS FOR AUTOMATED DESIGN OF COMPLEX STRUCTURES USING GENETIC PROGRAMMING, herein incorporated by reference in its entirety, used Genetic Programming (GP) to grow an xe2x80x9cembryonicxe2x80x9d circuit to a circuit that satisfies desired requirements. This approach was used for evolving a variety of circuits, including filters and computational circuits. An alternative encoding technique using a linear representation, which has the advantage of reduced computational load, has been used in for automated filter design.
With these extrinsic approaches, though, evolutions of analog circuits were performed in simulations, without concern of a physical implementation, but rather, as a proof-of-concept that evolution can lead to designs that compete or even exceed the performance of human designs. Although in principle, one can test their validity in circuits built from discrete components, or in an ASIC, no analog programmable devices exist that would support the implementation of the resulting design. Thus, these approaches do not provide a practical solution to intrinsic evolution.
Intrinsic evolution can speed-up the search for a solution circuit by a few orders of magnitude compared to evolution in software simulations, specifically if one simulates large, complex analog circuits, and if the circuit response is rapid. Moreover, since the software simulation relies on models of physical hardware with limited accuracy, a solution evolved in software may behave differently when downloaded in programmable hardware; such mismatches are avoided when evolution takes place directly in hardware. Further, unlike software evaluation where more complex circuitry and more accurate modeling takes longer to evaluate, hardware evolution scales well with both size of the circuits and model accuracy, thus providing less significant increases in evaluation time.
Although reconfigurable devices exist, they have a limited range of possible applications. On-chip evolution was demonstrated by A. Thompson, in Silicon Evolution, in Proceedings of Genetic Programming 1996 (GP96), MIT Press, herein incorporated by reference in its entirety, using a Field Programmable Gate Array or FPGA as a programmable digital device, and a Genetic Algorithm or GA as the evolutionary mechanism.
Such a technique using gate arrays, however, is not practical for analog circuit evolution. Logical gates are not good elementary building blocks for analog circuits as they are designed optimized for logical/binary behaviors. For example, transistor interconnections that are designed to facilitate digital logic signals and flows do not necessarily provide good analog response and signal flow. The usage of the gate array for evolution can result in exploitation by evolution, of parasitic and unintended signal paths and functioning modes for the components. As a result, circuits may evolve in one region of a chip that can not be replicated in other parts, or on other chips, although the same genetic code is used.
Moreover, conventional on chip evolution has not provided sufficient granularity for practical applications. While several levels of granularity are in use, the most common digital devices are configurable at the gate-level. In the analog programmable devices, such as in Field Programmable Analog Arrays or FPAAs, the reconfigurable active elements are Operational Amplifiers, which have only very coarse granularity and little functionality with good precision, thus having only a limited range of possible applications.
Computation by analog circuit has been lost as a technique for information processing because analog circuits were not easily programmable, and required precise components with no drifts. If the evolutionary mechanism and process proves sufficiently powerful for evolving complex analog circuits, then its combination with reconfigurable analog devices potentially will be able to capture the benefits of analog in new applications. As such, the potential of analog processing is much greater than what is able to be exploited today.
Analog circuitry has advantages in cost, size and power consumption (as compared to digital circuitry) and can directly process signals that are continual in time and amplitude. Even a single transistor has many functions such as generation of square, square-root, exponential and logarithmic functions, voltage-controlled current sources; analog multiplication of voltages, and short term and long term analog storage. As such, the basic combinations of transistors offer a rich repertoire of linear and nonlinear operators available for local and collective analog processing. Using evolution, the benefits of analog processing can be exploited, while its disadvantages reduced or even eliminated.
Also, it has been recognized by the inventors herein that evolutionary searches may perform significantly better with analog than with digital circuitry. A possible explanation lies in the fact that analog behaviors have relatively smoother spaces, which is better for the evolutionary search. Thus, new perspectives are possible: evolutionary searches offering automatic programming; sufficiently precise equivalent components could be obtained if the programmable analog components offer controllability of their operating points; and drifts that can be compensated for by adjusting operating points or, if the drifts are too strong, by a new search for a different optimal circuit configuration and operating point. Moreover, analog computation on simple low-power circuits can boost emerging applications areas of xe2x80x9csmart matterxe2x80x9d and distributed high bandwidth adaptive sensing.
Furthermore, a hardware implementation also offers a big advantage in evaluation time for a circuit; the time for evaluation is determined by the goal function. For example, considering an A/D converter operating at a 100 kHz sampling rate, the electronic response of the A/D converter is available within 10 microseconds, compared to 1 second on a computer running SPICE; this advantage increases with the complexity of the circuits. In this case, the 105 speedup would allow evaluations of populations of millions of individuals in seconds instead of days. Moreover, the higher the frequency at which a circuit needs to function, the shorter is its evaluation time, making the design of very high frequency circuits an excellent candidate for intrinsic evolutionary design.
Thus, a practical solution to intrinsic evolution for programming analog devices is desirable. Furthermore, a shift in the design approach, from reconfigurable devices, to evolution-oriented devices or evolvable devices would facilitate hardware evolvability.
The preferred embodiment provides a programmable transistor array or PTA, which is programmable at the transistor level. It is possible to conveniently form such an array of N-type and P-type complementary field effect transistors, although it may be formed of other type devices. The preferred embodiment of the present invention provides an evolvable circuit having a plurality of transistors having terminals, the transistors being coupled between a power source terminal and a power sink terminal so as to be capable of admitting power between the power source terminal and the power sink terminal. Transistor terminal to transistor terminal couplings are provided via reconfigurable switches.
In a preferred embodiment, the plurality of transistors are coupled together in a topology so that a permutation of switch states of the plurality of switches provides a majority of meaningful circuit connections for a selected transistor topology, the plurality of transistors being coupled so that there are less than a total number of possible transistor terminal to transistor terminal couplings. With this embodiment, the plurality of transistor terminals may be coupled so as to be capable of providing both analog and digital responses to input signals.
The evolvable circuit of the present invention may have at least one of the plurality of transistors having its control terminal coupled one of its first and second power terminals, at least one of the plurality of transistors having its control terminal coupled to the control terminal of another of the plurality transistors, or at least one of the plurality of transistors may have a bypass switch coupled across its power terminals. In one preferred embodiment, all these terminal couplings are present.
In further preferred embodiments, the plurality of transistors are arranged in a plurality of layers, each transistor of a layer being coupled to at least one transistor of an adjacent layer. Such an embodiment may have a first layer having the first power terminals of each of the first and second transistors coupled to the power source terminal; and have at least one intermediate layer having the first power terminals of the first and the second transistors coupled to the second power terminals of the first and second transistors of a preceding layer, respectively; and having the second power terminals of the first and second transistors coupled to the first terminal of a succeeding layer, respectively; and have a last layer having the second power terminals of the first and second transistors coupled to the power sink terminal.
The plurality of transistors may be arranged to form a module which may be connected via reconfigurable switches to other modules to provide solutions to more complex problems. In one embodiment, several modules may be arranged on a single chip so that modules disposed near a center of a module arrangement have a greater number of inter-module couplings than do modules near a periphery of the plurality of the arrangement. In some embodiments, inter-module coupling may be uniform across the array.
In some embodiments the reconfigurable switches may be transistors operated as ON/OFF switches. In other embodiments, the reconfigurable switches may be operated in gradual high/low states that provide variable conductance states. With this embodiment, the gradual switches may be controlled so that evolution provides a morphing process which can ultimately reach solutions with ON/OFF switch states.